package com.zhugang.week03;

import java.util.Stack;

/**
 * @program algorithms
 * @description: trap
 * @author: chanzhugang
 * @create: 2022/06/06 09:57
 */
public class Trap {

    public static void main(String[] args) {
        Trap trap = new Trap();
        int[] height = new int[]{4, 2, 0, 3, 2, 5};
        int res = trap.trap(height);
        System.out.println(res);
    }

    /**
     * 42. 接雨水
     *
     * @return
     */
    public int trap(int[] height) {
        /**
         * 暴力求解：O(n^2)
         * 每个柱子承载水量：min(左侧最高柱子lh，右侧最高柱子rh) - 这个柱子的高度h
         * 总的接水量 = 每个柱子承载的水量之和
         */
        int n = height.length;
        int result = 0;
        for (int i = 1; i < n - 1; i++) {
            int lh = 0;
            for (int j = 0; j < i; j++) {
                // 左侧最高值
                if (height[j] > lh) lh = height[j];
            }
            int rh = 0;
            for (int j = i + 1; j < n; j++) {
                // 右侧最高值
                if (height[j] > rh) rh = height[j];
            }
            int carry = Math.min(lh, rh) - height[i];
            if (carry < 0) carry = 0;
            result += carry;
        }
        return result;
    }

    /**
     * O(n)
     *
     * @param height
     * @return
     */
    public int trap2(int[] height) {
        /**
         * 前缀、后缀统计法
         */
        int n = height.length;
        // 前缀
        int[] leftMax = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            leftMax[i] = Math.max(max, height[i]);
            max = leftMax[i];
        }
        // 后缀
        int[] rightMax = new int[n];
        max = 0;
        for (int i = n - 1; i >= 0; i--) {
            rightMax[i] = Math.max(max, height[i]);
            max = rightMax[i];
        }
        int result = 0;
        for (int i = 1; i < n - 1; i++) {
            result += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return result;
    }

    /**
     * 单调栈法？ 没看明白
     *
     * @param height
     * @return
     */
    public int trap3(int[] height) {
        int n = height.length;
        int result = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            if (stack.isEmpty()) {
                stack.push(i);
                continue;
            }
            while (!stack.isEmpty()) {
                Integer top = stack.peek();
                if (height[top] >= height[i]) {
                    // 单调入栈
                    stack.push(i);
                    break;
                } else {
                    // 找到凹槽
                    top = stack.pop();
                    if (stack.isEmpty()) {
                        stack.push(i);
                        break;
                    }
                    int left = stack.peek();
                    int h = Math.min(height[left], height[i]) - height[top];
                    int w = i - left - 1;
                    result += h * w;
                }
            }
        }
        return result;
    }
}